/*************************************************************************
	> File Name: binary_tree.cpp
	> Author: 
	> Mail: 
	> Created Time: Fri 26 Jul 2024 08:22:06 PM CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct Node {
	int key;
	struct Node *left, *right;	
} Node;

Node *getNewNode(int key) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->key = key;
	p->left = p->right = nullptr;
	return p;
}

Node *insert(Node *root, int key) {
	if(root == nullptr) return getNewNode(key);
	if(rand() % 2) root->left = insert(root->left, key);
	else root->right = insert(root->right, key);
	return root;
}
Node *quene[15];
int head, tail;

void bfs(Node *root) {
	if(root == nullptr) return ;
	head = tail = 0;
	quene[tail++] = root;
	while(head < tail) {
		Node *node = quene[head];
		printf("\nnode : \n%d\n", node->key);
		if(node->left) {
			quene[tail++] = node->left;
			printf("node(%d)->%d(L)\n", node->key, node->left->key);
		}
		if(node->right) {
			quene[tail++] = node->right;
			printf("node(%d)->%d(R)\n", node->key, node->right->key);
		}
		printf("\n");
		head++;
	}
	return ;
}
int flag = 0;
void dfs(Node *root) {
	if(root == nullptr) return ;
	int start, end;
	flag += 1;
	start = flag;
	if(root->left) dfs(root->left);
	if(root->right) dfs(root->right);
	flag += 1;
	end = flag;
	printf("node(%d) : [%d, %d]\n", root->key, start, end);
}

void clear(Node *root) {
	if(root == nullptr) return ;
	clear(root->left);
	clear(root->right);
	free(root);
}

int main() {
	srand(time(0));
	Node *root = nullptr;
	for(int i = 0; i < 10; i++) {
		root = insert(root, rand() % 100);
	}
	bfs(root); // 广度遍历
	dfs(root); // 深度遍历
	clear(root);
	return 0;
}

